// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/string-builder-inl.h"

#include "src/isolate-inl.h"
#include "src/objects/fixed-array-inl.h"
#include "src/objects/js-array-inl.h"

namespace v8 {
namespace internal {

    template <typename sinkchar>
    void StringBuilderConcatHelper(String special, sinkchar* sink,
        FixedArray fixed_array, int array_length)
    {
        DisallowHeapAllocation no_gc;
        int position = 0;
        for (int i = 0; i < array_length; i++) {
            Object element = fixed_array->get(i);
            if (element->IsSmi()) {
                // Smi encoding of position and length.
                int encoded_slice = Smi::ToInt(element);
                int pos;
                int len;
                if (encoded_slice > 0) {
                    // Position and length encoded in one smi.
                    pos = StringBuilderSubstringPosition::decode(encoded_slice);
                    len = StringBuilderSubstringLength::decode(encoded_slice);
                } else {
                    // Position and length encoded in two smis.
                    Object obj = fixed_array->get(++i);
                    DCHECK(obj->IsSmi());
                    pos = Smi::ToInt(obj);
                    len = -encoded_slice;
                }
                String::WriteToFlat(special, sink + position, pos, pos + len);
                position += len;
            } else {
                String string = String::cast(element);
                int element_length = string->length();
                String::WriteToFlat(string, sink + position, 0, element_length);
                position += element_length;
            }
        }
    }

    template void StringBuilderConcatHelper<uint8_t>(String special, uint8_t* sink,
        FixedArray fixed_array,
        int array_length);

    template void StringBuilderConcatHelper<uc16>(String special, uc16* sink,
        FixedArray fixed_array,
        int array_length);

    int StringBuilderConcatLength(int special_length, FixedArray fixed_array,
        int array_length, bool* one_byte)
    {
        DisallowHeapAllocation no_gc;
        int position = 0;
        for (int i = 0; i < array_length; i++) {
            int increment = 0;
            Object elt = fixed_array->get(i);
            if (elt->IsSmi()) {
                // Smi encoding of position and length.
                int smi_value = Smi::ToInt(elt);
                int pos;
                int len;
                if (smi_value > 0) {
                    // Position and length encoded in one smi.
                    pos = StringBuilderSubstringPosition::decode(smi_value);
                    len = StringBuilderSubstringLength::decode(smi_value);
                } else {
                    // Position and length encoded in two smis.
                    len = -smi_value;
                    // Get the position and check that it is a positive smi.
                    i++;
                    if (i >= array_length)
                        return -1;
                    Object next_smi = fixed_array->get(i);
                    if (!next_smi->IsSmi())
                        return -1;
                    pos = Smi::ToInt(next_smi);
                    if (pos < 0)
                        return -1;
                }
                DCHECK_GE(pos, 0);
                DCHECK_GE(len, 0);
                if (pos > special_length || len > special_length - pos)
                    return -1;
                increment = len;
            } else if (elt->IsString()) {
                String element = String::cast(elt);
                int element_length = element->length();
                increment = element_length;
                if (*one_byte && !element->IsOneByteRepresentation()) {
                    *one_byte = false;
                }
            } else {
                return -1;
            }
            if (increment > String::kMaxLength - position) {
                return kMaxInt; // Provoke throw on allocation.
            }
            position += increment;
        }
        return position;
    }

    FixedArrayBuilder::FixedArrayBuilder(Isolate* isolate, int initial_capacity)
        : array_(isolate->factory()->NewFixedArrayWithHoles(initial_capacity))
        , length_(0)
        , has_non_smi_elements_(false)
    {
        // Require a non-zero initial size. Ensures that doubling the size to
        // extend the array will work.
        DCHECK_GT(initial_capacity, 0);
    }

    FixedArrayBuilder::FixedArrayBuilder(Handle<FixedArray> backing_store)
        : array_(backing_store)
        , length_(0)
        , has_non_smi_elements_(false)
    {
        // Require a non-zero initial size. Ensures that doubling the size to
        // extend the array will work.
        DCHECK_GT(backing_store->length(), 0);
    }

    bool FixedArrayBuilder::HasCapacity(int elements)
    {
        int length = array_->length();
        int required_length = length_ + elements;
        return (length >= required_length);
    }

    void FixedArrayBuilder::EnsureCapacity(Isolate* isolate, int elements)
    {
        int length = array_->length();
        int required_length = length_ + elements;
        if (length < required_length) {
            int new_length = length;
            do {
                new_length *= 2;
            } while (new_length < required_length);
            Handle<FixedArray> extended_array = isolate->factory()->NewFixedArrayWithHoles(new_length);
            array_->CopyTo(0, *extended_array, 0, length_);
            array_ = extended_array;
        }
    }

    void FixedArrayBuilder::Add(Object value)
    {
        DCHECK(!value->IsSmi());
        array_->set(length_, value);
        length_++;
        has_non_smi_elements_ = true;
    }

    void FixedArrayBuilder::Add(Smi value)
    {
        DCHECK(value->IsSmi());
        array_->set(length_, value);
        length_++;
    }

    int FixedArrayBuilder::capacity() { return array_->length(); }

    Handle<JSArray> FixedArrayBuilder::ToJSArray(Handle<JSArray> target_array)
    {
        JSArray::SetContent(target_array, array_);
        target_array->set_length(Smi::FromInt(length_));
        return target_array;
    }

    ReplacementStringBuilder::ReplacementStringBuilder(Heap* heap,
        Handle<String> subject,
        int estimated_part_count)
        : heap_(heap)
        , array_builder_(Isolate::FromHeap(heap), estimated_part_count)
        , subject_(subject)
        , character_count_(0)
        , is_one_byte_(subject->IsOneByteRepresentation())
    {
        // Require a non-zero initial size. Ensures that doubling the size to
        // extend the array will work.
        DCHECK_GT(estimated_part_count, 0);
    }

    void ReplacementStringBuilder::EnsureCapacity(int elements)
    {
        array_builder_.EnsureCapacity(Isolate::FromHeap(heap_), elements);
    }

    void ReplacementStringBuilder::AddString(Handle<String> string)
    {
        int length = string->length();
        DCHECK_GT(length, 0);
        AddElement(string);
        if (!string->IsOneByteRepresentation()) {
            is_one_byte_ = false;
        }
        IncrementCharacterCount(length);
    }

    MaybeHandle<String> ReplacementStringBuilder::ToString()
    {
        Isolate* isolate = Isolate::FromHeap(heap_);
        if (array_builder_.length() == 0) {
            return isolate->factory()->empty_string();
        }

        Handle<String> joined_string;
        if (is_one_byte_) {
            Handle<SeqOneByteString> seq;
            ASSIGN_RETURN_ON_EXCEPTION(
                isolate, seq, isolate->factory()->NewRawOneByteString(character_count_),
                String);

            DisallowHeapAllocation no_gc;
            uint8_t* char_buffer = seq->GetChars(no_gc);
            StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(),
                array_builder_.length());
            joined_string = Handle<String>::cast(seq);
        } else {
            // Two-byte.
            Handle<SeqTwoByteString> seq;
            ASSIGN_RETURN_ON_EXCEPTION(
                isolate, seq, isolate->factory()->NewRawTwoByteString(character_count_),
                String);

            DisallowHeapAllocation no_gc;
            uc16* char_buffer = seq->GetChars(no_gc);
            StringBuilderConcatHelper(*subject_, char_buffer, *array_builder_.array(),
                array_builder_.length());
            joined_string = Handle<String>::cast(seq);
        }
        return joined_string;
    }

    void ReplacementStringBuilder::AddElement(Handle<Object> element)
    {
        DCHECK(element->IsSmi() || element->IsString());
        EnsureCapacity(1);
        DisallowHeapAllocation no_gc;
        array_builder_.Add(*element);
    }

    IncrementalStringBuilder::IncrementalStringBuilder(Isolate* isolate)
        : isolate_(isolate)
        , encoding_(String::ONE_BYTE_ENCODING)
        , overflowed_(false)
        , part_length_(kInitialPartLength)
        , current_index_(0)
    {
        // Create an accumulator handle starting with the empty string.
        accumulator_ = Handle<String>::New(ReadOnlyRoots(isolate).empty_string(), isolate);
        current_part_ = factory()->NewRawOneByteString(part_length_).ToHandleChecked();
    }

    int IncrementalStringBuilder::Length() const
    {
        return accumulator_->length() + current_index_;
    }

    void IncrementalStringBuilder::Accumulate(Handle<String> new_part)
    {
        Handle<String> new_accumulator;
        if (accumulator()->length() + new_part->length() > String::kMaxLength) {
            // Set the flag and carry on. Delay throwing the exception till the end.
            new_accumulator = factory()->empty_string();
            overflowed_ = true;
        } else {
            new_accumulator = factory()->NewConsString(accumulator(), new_part).ToHandleChecked();
        }
        set_accumulator(new_accumulator);
    }

    void IncrementalStringBuilder::Extend()
    {
        DCHECK_EQ(current_index_, current_part()->length());
        Accumulate(current_part());
        if (part_length_ <= kMaxPartLength / kPartLengthGrowthFactor) {
            part_length_ *= kPartLengthGrowthFactor;
        }
        Handle<String> new_part;
        if (encoding_ == String::ONE_BYTE_ENCODING) {
            new_part = factory()->NewRawOneByteString(part_length_).ToHandleChecked();
        } else {
            new_part = factory()->NewRawTwoByteString(part_length_).ToHandleChecked();
        }
        // Reuse the same handle to avoid being invalidated when exiting handle scope.
        set_current_part(new_part);
        current_index_ = 0;
    }

    MaybeHandle<String> IncrementalStringBuilder::Finish()
    {
        ShrinkCurrentPart();
        Accumulate(current_part());
        if (overflowed_) {
            THROW_NEW_ERROR(isolate_, NewInvalidStringLengthError(), String);
        }
        return accumulator();
    }

    void IncrementalStringBuilder::AppendString(Handle<String> string)
    {
        ShrinkCurrentPart();
        part_length_ = kInitialPartLength; // Allocate conservatively.
        Extend(); // Attach current part and allocate new part.
        Accumulate(string);
    }
} // namespace internal
} // namespace v8
